package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

/**
 * @Author: tgy
 * @Date: 2/3/21 2:08 PM
 */
public class _06_找二叉树中的最大搜索二叉树子树 {

    private static class TreeInfo {

        TreeNode root;

        int maxVal;
        int minVal;
        // 记录这颗二叉搜索树元素的个数
        int count;

        public TreeInfo(TreeNode root) {
            this.root = root;
        }
    }

    /**
     *
     * 跟构成子树的根节点与返回的搜索二叉树能构成搜索二叉树的条件
     *
     *  root.left == TreeInfo.root
     *
     *  root.val > TreeInfo.mavVal
     *
     *
     * @param root
     * @return
     */
    public static TreeNode findMaxSearchTree(TreeNode root) {

        if (root == null || (root.left == null && root.right == null)) {

            return root;
        }


        return find(root).root;
    }

    public static TreeInfo find(TreeNode node) {


        if (node.left == null && node.right == null) {

            TreeInfo treeInfo = new TreeInfo(node);
            treeInfo.maxVal = node.val;
            treeInfo.minVal = node.val;
            treeInfo.count = 1;
            return treeInfo;
        }

        TreeInfo leftTreeInfo = null, rightTreeInfo = null;
        if (node.left != null) {

            leftTreeInfo = find(node.left);
        }

        if (node.right != null) {

            rightTreeInfo = find(node.right);
        }

        if (leftTreeInfo != null && rightTreeInfo != null) {



            if ((node.left == leftTreeInfo.root && node.val > leftTreeInfo.maxVal)) {

                if ((node.right == rightTreeInfo.root && node.val < rightTreeInfo.minVal)) {

                    leftTreeInfo.root = node;
                    leftTreeInfo.maxVal = rightTreeInfo.maxVal;
                    leftTreeInfo.count += rightTreeInfo.count;
                    return leftTreeInfo;
                }
            }

            return leftTreeInfo.count > rightTreeInfo.count? leftTreeInfo:rightTreeInfo;
        }

        if (leftTreeInfo == null) {

            if ((node.right == rightTreeInfo.root && node.val < rightTreeInfo.minVal)) {

                rightTreeInfo.root = node;
                rightTreeInfo.minVal = node.val;
                rightTreeInfo.count += 1;
                return rightTreeInfo;
            }
            return rightTreeInfo;
        }

        if (rightTreeInfo == null) {

            if ((node.left == leftTreeInfo.root && node.val > leftTreeInfo.maxVal)) {

                leftTreeInfo.root = node;
                leftTreeInfo.maxVal = node.val;
                leftTreeInfo.count += 1;
                return leftTreeInfo;
            }

            return leftTreeInfo;
        }


        return null;
    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(6);

        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(4);
        root.right.left.left.left = new TreeNode(2);
        root.right.left.left.right = new TreeNode(5);
        root.right.left.right = new TreeNode(14);
        root.right.left.right.left = new TreeNode(11);
        root.right.left.right.right = new TreeNode(15);

        root.right.right = new TreeNode(16);
        root.right.right.left = new TreeNode(13);
        root.right.right.right = new TreeNode(20);

        TreeNode node = findMaxSearchTree(root);

        System.out.println(node.val);
    }
}
